package com.shangguigu.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/10/28
 * @description: 赫夫曼树--文件压缩算法中最好的算法
 * 树的带权路径长度（WPL）：所有叶子节点的带权路径长度之和最小。
 */
public class HuffmanTree {

	/**
	 * 创建赫夫曼树
	 * 思路：
	 * 1.排序（从小到大）；
	 * 2.将最小的两个生成新的二叉树，并从数组中移除，然后将根节点的权加入到新的数组中；
	 * 3.循环上两步骤
	 */
	public TreeNode createHuffmanTree(int[] arr) {
		if (arr == null || arr.length == 0) {
			return null;
		}
		///1.构造二叉树节点
		List<TreeNode> list = new ArrayList<>();
		for (int item :
				arr) {
			list.add(new TreeNode(item));
		}
		///2.从小到大排序
		Collections.sort(list, nodeComparable());
		///3.循环处理：将最小的两个节点组装成新的二叉树并从数组中删除；该新的二叉树添加到数组中
		while (list.size() > 1) {
			TreeNode min2Node = list.remove(1);
			TreeNode minNode = list.remove(0);
			TreeNode newNode = new TreeNode(min2Node.val + minNode.val);
			newNode.left=min2Node;
			newNode.right=minNode;
			list.add(newNode);
			Collections.sort(list, nodeComparable());
		}
		return list.get(0);
	}

	/**
	 * 封装排序规则
	 * @return
	 */
	private Comparator<TreeNode> nodeComparable(){
		return new Comparator<TreeNode>() {
			@Override
			public int compare(TreeNode o1, TreeNode o2) {
				return o1.val - o2.val;
			}
		};
	}

	/**
	 *
	 */
	@Test
	public void testCreateHuffmanTree() {
		int[] arr = {13, 7, 8, 3, 29, 6, 1};
		TreeNode huffmanTree = createHuffmanTree(arr);

	}
}
